/*  Copyright 2010 Daniel Brasil Magnani
 *  Created on: Dec 20, 2010
 *      Author: daniel
 */

#include <algorithm>
#include "constructive.h"

void Constructive::CounterVector(
    const std::vector<Constraint> &constraint_list,
    std::vector<Cost> *cost_counter) {
  for (int j = 0; j < constraint_size_; j++) {
    (*cost_counter)[j].priority = 0;
    (*cost_counter)[j].nonpriority = 0;
    for (int k = 0; k < constraint_list[j].p-1; k++) {
      if ( solution_size_-k > 0 ) {
        if ( solution_[solution_size_-k-1].constraints[j] == 1 ) {
          if ( constraint_list[j].priority == 1 )
            (*cost_counter)[j].priority++;
          else
            (*cost_counter)[j].nonpriority++;
        }
      }
    }
  }
}

void Constructive::UtilizationRate(
    const std::vector<Constraint> &constraint_list,
    std::vector<Car> *S) {
  for (int i = 0; i < constraint_size_; i++ )
    utilization_rate_[i] = 0;
  for (int i = 0; i < (*S).size(); i++) {
    for (int j = 0; j < constraint_size_; j++)
      if ( (*S)[i].constraints[j] == 1)
        utilization_rate_[j]++;
  }

  for ( int i = 0; i < constraint_size_ ; i++ )
    utilization_rate_[i] = (static_cast<float>(utilization_rate_[i])/
                            static_cast<float>((*S).size()))/
                           (static_cast<float>(constraint_list[i].n)/
                            static_cast<float>(constraint_list[i].p));

  for (int i = 0; i < (*S).size(); i++) {
    (*S)[i].utilization_rate = 0;
    for ( int j = 0; j < constraint_list.size(); j++ ) {
      if ( constraint_list[j].priority == 0 )
        break;
      if ( (*S)[i].constraints[j] == 1)
        (*S)[i].utilization_rate += utilization_rate_[j];
    }
  }
}

Cost Constructive::CostFrontInsert(
    const std::vector<Constraint> &constraint_list,
    const std::vector<Cost> &cost_counter,
    const Car temp_car) {
  Cost cost;
  cost.priority = 0;
  cost.nonpriority = 0;
  for (int j = 0; j < constraint_size_; j++) {
    if ( constraint_list[j].priority == 1 ) {
      if ( cost_counter[j].priority >= constraint_list[j].n ) {
        if (temp_car.constraints[j] == 1)
          cost.priority += ((cost_counter[j].priority -
                             constraint_list[j].n) + 1);
        else
          cost.priority += (cost_counter[j].priority - constraint_list[j].n);
      }
    } else {
      if ( cost_counter[j].nonpriority >= constraint_list[j].n ) {
        if (temp_car.constraints[j] == 1)
          cost.nonpriority += ((cost_counter[j].nonpriority -
                                constraint_list[j].n) + 1);
        else
          cost.nonpriority += (cost_counter[j].nonpriority -
                               constraint_list[j].n);
      }
    }
  }

  return cost;
}

Constructive::Constructive(const std::vector<Car> &yesterday_cars,
                           const std::vector<Car> &today_cars,
                           const std::vector<Constraint> &constraint_list) {
  cost_.priority = 0;
  cost_.nonpriority = 0;
  solution_.reserve(today_cars.size()+yesterday_cars.size());
  utilization_rate_.reserve(constraint_list.size());
  constraint_size_ = constraint_list.size();
  solution_size_ = solution_.size();
  yesterday_size_ = yesterday_cars.size();
}

std::vector<Car> Constructive::get_solution() {
  return solution_;
}

int Constructive::Execute(const std::vector<Car> &yesterday_cars,
                          const std::vector<Car> &today_cars,
                          const std::vector<Constraint> &constraint_list) {
  std::vector<Car> S;
  std::vector<Car>::iterator car_iterator;
  std::vector<Cost> cost_counter;
  std::vector<Cost> cars_violations;
  std::vector<int> LRC;
  Cost violations_min;
  Cost violations;
  violations.priority = 0;
  violations.nonpriority = 0;
  int v;

  S.reserve(today_cars.size());
  LRC.reserve(today_cars.size());
  cars_violations.reserve(today_cars.size());
  cost_counter.reserve(constraint_size_);
  copy(yesterday_cars.begin(), yesterday_cars.end(), back_inserter(solution_));
  copy(today_cars.begin(), today_cars.end(), back_inserter(S));
  solution_size_ = solution_.size();

  while ( S.size() != 0 ) {
    violations_min.priority = INT_MAX;
    violations_min.nonpriority = INT_MAX;
    CounterVector(constraint_list, &cost_counter);

    for (int i = 0; i < S.size(); i++) {
      cars_violations[i].priority = 0;
      cars_violations[i].nonpriority = 0;
    }
    LRC.clear();
    UtilizationRate(constraint_list, &S);

    for (int i = 0; i < S.size(); i++) {
      violations.priority = 0;
      violations.nonpriority = 0;

      violations = CostFrontInsert(constraint_list, cost_counter, S[i]);

      if ( (violations.priority < violations_min.priority) ||
          ((violations.priority == violations_min.priority) &&
          (violations.nonpriority <= violations_min.nonpriority)) ) {
        v = i;
        cars_violations[i].priority = violations.priority;
        cars_violations[i].nonpriority = violations.nonpriority;
        violations_min.priority = violations.priority;
        violations_min.nonpriority = violations.nonpriority;
      }
    }

    float max_utilization_rate = 0;
    for (int i = 0; i < S.size(); i++) {
      if ( (cars_violations[i].priority == violations_min.priority) &&
            cars_violations[i].nonpriority == violations_min.nonpriority ) {
        if ( S[i].utilization_rate > max_utilization_rate )
          max_utilization_rate = S[i].utilization_rate;
      }
    }

    for (int i = 0; i < S.size(); i++) {
      if ( (cars_violations[i].priority == violations_min.priority) &&
            cars_violations[i].nonpriority == violations_min.nonpriority ) {
        if ( S[i].utilization_rate == max_utilization_rate ) {
          LRC.push_back(i);
        }
      }
    }

    v = LRC[rand()%LRC.size()];

    solution_.push_back(S[v]);
    car_iterator = S.begin();
    advance(car_iterator, v);
    S.erase(car_iterator);
    solution_size_ = solution_.size();
  }
  return true;
}
